/**
 *
 * @author Anastasiya
 *
 */

#include "ozawa.h"
#include "printing.h"
#include "util.h"
#include <ogdf/basic/basic.h>
#include <ogdf/basic/Graph_d.h>
#include <ogdf/basic/List.h>
#include <ogdf/planarity/FastPlanarSubgraph.h>
#include <ogdf/basic/simple_graph_alg.h>
#include <ogdf/basic/extended_graph_alg.h>
#include <direct.h>
#include <windows.h>
#include <time.h>
#include <iostream>
#include <map>
#include <string>

using namespace std;

extern Printer* printer;


const int OzawaAlgorithm::ST_NUMBERING_FAILED = 1000;

const string OzawaAlgorithm::PROCESS_MESSAGE_READING_GRAPH = "Reading graph";
const string OzawaAlgorithm::PROCESS_MESSAGE_MAKING_ST_NUMBERING = "Making st-numbering";
const string OzawaAlgorithm::PROCESS_MESSAGE_COMPUTING_LEAFS = "Computing PQ-Trees leafs";
const string OzawaAlgorithm::PROCESS_MESSAGE_COMPUTING_REDUCE_LEAFS = "Computing leafs for reduce";
const string OzawaAlgorithm::PROCESS_MESSAGE_COMPUTING_PQ_TREES = "Computing PQ-Trees";
const string OzawaAlgorithm::PROCESS_MESSAGE_INITIALIZING_FIRST_TREE = "Initializing T1";
const string OzawaAlgorithm::PROCESS_MESSAGE_REDUCING_TREE = "Reducing T";
const string OzawaAlgorithm::PROCESS_MESSAGE_DELETING_EDGES = "Deleting edges";
const string OzawaAlgorithm::PROCESS_MESSAGE_WRITING_RESULT = "Writing result";

const string OzawaAlgorithm::PROCESS_ERROR_NO_SUCH_FILE = "There is no such file. ";
const string OzawaAlgorithm::PROCESS_ERROR_MUST_CONTAINT_MORE_THEN_3_NODES = "Graph must contains at least 3 nodes: ";
const string OzawaAlgorithm::PROCESS_ERROR_MUST_BE_SIMPLE = "Graph must be simple and biconnected: ";
const string OzawaAlgorithm::PROCESS_ERROR_ST_NUMBERING = "ST-Numbering failed: ";
const string OzawaAlgorithm::PROCESS_ERROR_UNKNOWN_ERROR = "Some error occures: ";
const string OzawaAlgorithm::PROCESS_ERROR_REDUCING_FAILED = "Reducing failed";
const string OzawaAlgorithm::PROCESS_ERROR_EXCEPTION = "Some exception occures: ";

const string OzawaAlgorithm::ALGORITHM_NAME = "Ozawa";

OzawaAlgorithm::OzawaAlgorithm(){
	name = ALGORITHM_NAME;
}

string OzawaAlgorithm::getName(){
	return name;
}

OzawaAlgorithm::~OzawaAlgorithm(){
}

TestResult* OzawaAlgorithm::execute(string resultPath, string file){

	printer->testStarted(file);

	string fileName = getFileName(file);
	if(fileName == ""){
		printer->logError(PROCESS_ERROR_NO_SUCH_FILE, file);
		printer->testFailed(file);
		return NULL;
	}

	try{
		// Reading graph
		printer->logEvent(PROCESS_MESSAGE_READING_GRAPH);
		Graph* g = readGraph(file);

		if(g->numberOfNodes() < 3){
			// Check if graph have at least 3 nodes
			printer->logError(PROCESS_ERROR_MUST_CONTAINT_MORE_THEN_3_NODES, file);
			printer->testFailed(file);
			return NULL;
		}

		if(!isBiconnected(*g) || !isSimple(*g)){
			// Test if graph simple and biconnected. If not, st-numbering process will fail
			printer->logError(PROCESS_ERROR_MUST_BE_SIMPLE, file);
			printer->testFailed(file);
			return NULL;
		}

		clock_t startTime = clock();

		NodeArray<int>* stNumbering;
		try{
			printer->logEvent(PROCESS_MESSAGE_MAKING_ST_NUMBERING);
			// Compute st-numbering
			stNumbering = computeStNumbering(g);
		}catch(int exceptionCode){
			// There is some cases when ogdf's st-numbering fails without any messages
			if(exceptionCode == ST_NUMBERING_FAILED){
				printer->logError(PROCESS_ERROR_ST_NUMBERING, file);
				printer->testFailed(file);
				return NULL;
			}else{
				printer->logError(PROCESS_ERROR_UNKNOWN_ERROR, file);
				printer->testFailed(file);
				return NULL;
			}
		}

		map<node, PQTreeLeafs*> nodesPQTreeLeafs;
		map<node, PQTreeLeafs*> reducingPQTreeLeafs;
		Array<node> stNumberedNodes(g->numberOfNodes());
		printer->logEvent(PROCESS_MESSAGE_COMPUTING_LEAFS);
		// Computing PQ-leaves for each node. This leaves will be used for PQ-trees building
		computePQTreeLeaves(g, stNumbering, &nodesPQTreeLeafs, &stNumberedNodes);
		printer->logEvent(PROCESS_MESSAGE_COMPUTING_REDUCE_LEAFS);
		// Computing PQ-leaves which will be used for PQ-tree reducing.
		computeLeavesForReduce(g, &nodesPQTreeLeafs, &reducingPQTreeLeafs);

		int ind;
		PlanarSubgraphPQTree tree;

		printer->logEvent(PROCESS_MESSAGE_COMPUTING_PQ_TREES);
		SList<PQLeafKey<edge, whaInfo*, bool>*> edgesToDelete;
		// Start tree building-reducing process
		forall_arrayindices(ind, stNumberedNodes){
			node n = stNumberedNodes[ind];
			PQTreeLeafs* leafs = nodesPQTreeLeafs[n];
			PQTreeLeafs* reduceLeaves = reducingPQTreeLeafs[n];
			if(ind == 0){
				printer->logEvent(PROCESS_MESSAGE_INITIALIZING_FIRST_TREE);
				// Build first tree (T1)
				tree.Initialize(*leafs);
			}else{
				char indAsString[10]="";
				_itoa_s(ind, indAsString, sizeof(indAsString), 10); 
				printer->logEvent(PROCESS_MESSAGE_REDUCING_TREE + string(indAsString));
				SList<PQLeafKey<edge, whaInfo*, bool>*> eliminatedKeys;

				// Tests if we can reduce tree (Tn)
				if(tree.Reduction(*reduceLeaves, eliminatedKeys)){
					// Accumulates edges to be deleted from graph
					edgesToDelete.conc(eliminatedKeys);
					// Replaces pertient root with leafs corresponded to node n
					tree.ReplaceRoot(*leafs);
					tree.emptyAllPertinentNodes();
				}else{
					printer->logEvent(PROCESS_ERROR_REDUCING_FAILED);
					break;
				}
			}
		}

		printer->logEvent(PROCESS_MESSAGE_DELETING_EDGES);
		// Deletes accumulated edges from graph
		deleteEdges(g, &edgesToDelete);

		clock_t endTime = clock();

		createPathIfNotExists(resultPath);
		string resultFileName = concatPath(resultPath, fileName);
		printer->logEvent(PROCESS_MESSAGE_WRITING_RESULT);
		// Writes result in GML
		g->writeGML(resultFileName.c_str());
		printer->testEnded(file);

		double diffticks = endTime - startTime;
		__int64 timeElapsed = (__int64)((diffticks * 1000) / CLOCKS_PER_SEC);


		TestResult* result = new TestResult(timeElapsed * 1000 * 1000, edgesToDelete.size());

		// Cleaning
		tree.Cleanup();
		delete g;
		delete stNumbering;
		SListConstIterator<PQLeafKey<edge, whaInfo*, bool>*> edges = edgesToDelete.begin();
		while(edges != edgesToDelete.end()){
			delete *edges;
			edges++;
		}
		map<node, PQTreeLeafs*>::iterator leavesIterator = nodesPQTreeLeafs.begin();
		while(leavesIterator != nodesPQTreeLeafs.end()){
			delete leavesIterator->second;
			leavesIterator++;
		}
		leavesIterator = reducingPQTreeLeafs.begin();
		while(leavesIterator != reducingPQTreeLeafs.end()){
			delete leavesIterator->second;
			leavesIterator++;
		}

		return result;
	}catch(int){
		printer->logError(PROCESS_ERROR_EXCEPTION, file);
	}
	return NULL;
}

string OzawaAlgorithm::getFileName(string file){
	WIN32_FIND_DATA findFileData;
	HANDLE hFind;

	hFind = FindFirstFile(file.c_str(), &findFileData);
	if(hFind == INVALID_HANDLE_VALUE){
		FindClose(hFind);
		return "";
	}else{
		FindClose(hFind);
		return string(findFileData.cFileName);
	}
}


/**
 *
 * Reads graph from file. Returns pointer to created graph
 *
 */
Graph* OzawaAlgorithm::readGraph(string filename){
	Graph* g = new Graph();
	g -> readGML(filename.c_str());
	return g;
}

/**
 *
 * Deletes edges (edgesToDelete) from graph (g)
 *
 */
void OzawaAlgorithm::deleteEdges(Graph* g, SList<PQLeafKey<edge, whaInfo*, bool>*>* edgesToDelete){
	SListConstIterator<PQLeafKey<edge, whaInfo*, bool>*> edges = edgesToDelete->begin();
	while(edges != edgesToDelete->end()){
		g->delEdge(((PQLeafKey<edge, whaInfo*, bool>*)*edges)->userStructKey());
		edges++;
	}
}

/**
 *
 * Computes st-numbering for graph g. Returns pointer to NodeArray<int> contains numbering
 *
 */
NodeArray<int>* OzawaAlgorithm::computeStNumbering(Graph* g){
	NodeArray<int>* stNumbering = new NodeArray<int>(*g, 0);
	int n = stNumber(*g, *stNumbering, g->firstNode(), g->lastNode(), false);
	if(n == 0){
		throw ST_NUMBERING_FAILED;
	}
	OGDF_ASSERT_IF(dlConsistencyChecks, testSTnumber(*g,*stNumbering, n));
	return stNumbering;
}


/**
 *
 * Computes leaves wivh will be used for reducing PQ-tree. Computes leaves for each graph node.
 *
 */
void OzawaAlgorithm::computeLeavesForReduce(Graph* g, map<node, PQTreeLeafs*>* treeLeavesMap, map<node, PQTreeLeafs*>* reduceLeavesMap){
	node n;
	forall_nodes(n, *g){
		SListIterator<PlanarPQTreeLeaf*> it;
		for (it = (*treeLeavesMap)[n]->begin(); it.valid(); ++it)
		{
			PlanarPQTreeLeaf* leaf = *it;
			EdgeElement* edgeInfo = leaf->userStructKey();
			node oppositeNode = edgeInfo->opposite(n);

			if((*reduceLeavesMap)[oppositeNode] == NULL){
				(*reduceLeavesMap)[oppositeNode] = new PQTreeLeafs();
			}
			(*reduceLeavesMap)[oppositeNode]->pushFront(leaf);
		}
	}
}

/**
 *
 * Computes PQ-tree leaves for each node. These leaves will be used for PQ-tree building 
 *
 */
void OzawaAlgorithm::computePQTreeLeaves(Graph* g, NodeArray<int>* stNumbering, map<node, PQTreeLeafs*>* leafsMap, Array<node>* stNumberedNodes){
	node n;
	forall_nodes(n, *g){
		(*leafsMap)[n] = computePQTreeLeaves(&n, stNumbering);
		int nodeStNumber = (*stNumbering)[n];
		(*stNumberedNodes)[nodeStNumber - 1] = n;
	}
}

/**
 *
 * Computes PQ-tree leaves for node.
 *
 */
PQTreeLeafs* OzawaAlgorithm::computePQTreeLeaves(node* n, NodeArray<int>* stNumbering){
	PQTreeLeafs* leafsForNode = new PQTreeLeafs();
	edge e;
	forall_adj_edges(e, *n){
		if ((*stNumbering)[e->opposite(*n)] > (*stNumbering)[*n])
		{
			PlanarPQTreeLeaf * L = new PlanarPQTreeLeaf(e);
			leafsForNode->pushFront(L);
		}
	}
	return leafsForNode;
}

